/**
 * 归并排序入口
 * @description
 * @author luyaxiang
 * @date 2021/09/22
 * @param {*} arr 原数组
 * @param {*} l 左侧
 * @param {*} r 右侧
 */
// function mergeSort(arr, l, r) {
//   if (l >= r) return;
//   const mid = (l + r) >> 1;
//   mergeSort(arr, l, mid); // 1.排序左侧
//   mergeSort(arr, mid + 1, r); // 2.排序右侧
//   mergeTwoIntervals(arr, l, mid, mid + 1, r); // 3.合并两个区间
//   return arr;
// }

// /**
//  * 合并两个区间
//  * @description
//  * @author luyaxiang
//  * @date 2021/09/22
//  * @param {*} arr 原数组
//  * @param {*} l1 左1
//  * @param {*} r1 右1
//  * @param {*} l2 左2
//  * @param {*} r2 右2
//  */
// function mergeTwoIntervals(arr, l1, r1, l2, r2) {
//   const temp = []; // 开辟一个临时空间、长度：r2 - l1 + 1;
//   let i = l1;
//   let j = l2;
//   let k = 0;
//   while(i <= r1 || j <= r2) {
//     if ((i <= r1 && arr[i] <= arr[j]) || (j > r2)) { // 左边区间
//       temp[k] = arr[i];
//       k++;
//       i++;
//     } else { // 右边
//       temp[k++] = arr[j++]
//     }
//   }
//   // 需要把temp里面，重新覆盖回arr中
//   for (var ii = l1; ii<= r2; ii++) {
//     arr[ii] = temp[ii - l1];
//   }
// }


// const a = [0, 2, 1, -6, 7, 9, 10, 3, 5];
// console.info(mergeSort(a, 0, a.length - 1))


/** ----------------------------------------- 练习开始 ----------------------------------------- */


function mergeSort(arr, l, r) {
  if (l >= r) return;
  const mid = (l + r) >> 1;
  mergeSort(arr, l, mid);
  mergeSort(arr, mid + 1, r);
  mergeTwoIntervals(arr, l, mid, mid + 1, r)
  return arr;
}

function mergeTwoIntervals(arr, l1, r1, l2, r2) {
  const temp = [];
  let i = l1;
  let j = l2;
  let k = 0;
  while(i <= r1 && j <= r2) {
    if (arr[i] <= arr[j]) {
      temp[k++] = arr[i++];
    } else {
      temp[k++] = arr[j++]
    }
  }
  while(i <= r1) temp[k++] = arr[i++];
  while(j <= r2) temp[k++] = arr[j++];
  for(var ii = l1; ii <= r2; ii++) {
    arr[ii] = temp[ii - l1]
  }
}
const a = [0, 2, 1, -6, 7, 9, 10, 3, 5];
console.info(mergeSort(a, 0, a.length - 1))
/** ----------------------------------------- 练习结束 ----------------------------------------- */



